public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        // System.out.println(test.minimumDeleteSum("delete", "leet"));

        int[] nums1 = new int[]{1,2,3,2,1};
        int[] nums2 = new int[]{3,2,1,4,7};
        System.out.println(test.findLength(nums1, nums2));
    }

    public int minimumDeleteSum(String s1, String s2) {
        /**
         * 两个字符串的最小ASCII删除和
         * 状态表示：
         *  dp[i][j]表示s1[0,i]范围 与 s2[0,j]范围 最长公共子序列的ASCII码值总和
         * 状态转移方程：
         *
         * 初始化：
         *
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  return dp[m-1][n-1];
         * 一次过！本题所应用到的思想就是将题目转换为已知内容进行求解，即对题目进行二次转换。
         * 这个思想非常重要！
         * */
        // 1 预处理
        int m = s1.length();
        int n = s2.length();
        int total = 0;
        for(int k = 0; k < m; k++) {
            total += (int)s1.charAt(k);
        }
        for(int k = 0; k < n; k++) {
            total += (int)s2.charAt(k);
        }
        // 2 创建dp表
        int[][] dp = new int[m][n];
        // 3 初始化
        for(int k = 0; k < m; k++) {
            if(s1.substring(0, k+1).contains(String.valueOf(s2.charAt(0)))) {
                dp[k][0] = (int)s2.charAt(0);
            }
        }
        for(int k = 0; k < n; k++) {
            if(s2.substring(0, k+1).contains(String.valueOf(s1.charAt(0)))) {
                dp[0][k] = (int)s1.charAt(0);
            }
        }
        // 4 填表
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = dp[i-1][j-1] + (int)s1.charAt(i);
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        // 5 返回值
        return total - dp[m-1][n-1] * 2;
    }

    public int findLength(int[] nums1, int[] nums2) {
        /**
         * 最长重复子数组
         * 本来只打算做一题，但是看到这一题也比较简单，于是顺带也做了
         * 状态表示：
         *  dp[i][j]表示nums1数组以i下标为结尾的所有子数组与 nums2数组以j下标为结尾的所有子数组，这两个范围最长公共子数组的长度
         * 状态转移方程：
         *  if(nums1[i] == nums2[j]) {
         *      dp[i][j] = dp[i-1][j-1] + 1;
         *  }
         * 初始化：
         *  使用虚拟位置法进行初始化
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  return 表中最大值
         * */
        // 1 预处理
        int m = nums1.length;
        int n = nums2.length;
        // 2 创建dp表
        int[][] dp = new int[m+1][n+1];
        // 3 初始化
        // 4 填表
        int ret = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if(ret < dp[i][j]) {
                        ret = dp[i][j];
                    }
                }
            }
        }
        // 5 返回值
        return ret;
    }
}
